package com.lun.medium;

import com.lun.util.BinaryTree.TreeNode;

public class DeleteNodeInABST {
	
	//方法一：我写的
    public TreeNode deleteNode(TreeNode root, int key) {
    	
    	TreeNode[] result = find(root, key);
    	
    	if(result != null) {

    		TreeNode parent = result[0], target = result[1];
    		TreeNode fakeRoot = null;
    		
    		if(parent == null) {//删除根节点，弄个假根节点，原根节点成为它的左子树
    			fakeRoot = new TreeNode(Integer.MAX_VALUE, root, null);
    		}
    		
			if(target.left != null && target.right != null) {//既有左子树，有右子树
				TreeNode replaceOne = findReplaceOneFromRight(target, target.right);
				target.val = replaceOne.val;
			}else {
				removeEasyOne(parent == null ? fakeRoot: parent, target);
			}
		
    		if(parent == null) {//删除根节点的情况
    			root = fakeRoot.left;
    			fakeRoot.left = null;
    		}
    	}
    	
        return root;
    }
    
    private TreeNode[] find(TreeNode root, int key) {    	
    	TreeNode last = null, curr = root;
    	
    	while(curr != null) {
    		
    		if(key < curr.val) {
    			last = curr;
    			curr = curr.left;
    		}else if(curr.val < key){
    			last = curr;
    			curr = curr.right;
    		}else {
    			return new TreeNode[] {last, curr};
    		}
    	}

    	return null;
    }
    
    /**
     * 
     * target是叶子节点，target只有左子树，target只有右子数，这三种情况可以用链表式方法的删除节点
     * 
     */
    private void removeEasyOne(TreeNode parent, TreeNode target) {
		if(target.left == null && target.right == null) {//target是叶子节点
			if(parent.left == target){
				parent.left = null;
			}else {
				parent.right = null;
			}
		}else if(target.left != null && target.right == null){//target只有左子树
			if(parent.left == target){
				parent.left = target.left;
				target.left = null;
			}else {
				parent.right = target.left;
				target.left = null;
			}
			
		}else if(target.left == null && target.right != null){//target只有右子数
			if(parent.left == target){
				parent.left = target.right;
				target.right = null;
			}else {
				parent.right = target.right;
				target.right = null;
			}
		}
    }
    
    //查找右子树的最小值
    private TreeNode findReplaceOneFromRight(TreeNode last, TreeNode child) {
    	if(child == null) return null;
    	
    	while(child.left != null) {//
    		last = child;
    		child = child.left;
    	}
    	removeEasyOne(last, child);
    	return child;
    }

    //方法二：别人写的，递归版，精简优雅了许多
    public TreeNode deleteNode2(TreeNode root, int key) {
        if(root == null){
            return null;
        }
        if(key < root.val){
            root.left = deleteNode2(root.left, key);
        }else if(key > root.val){
            root.right = deleteNode2(root.right, key);
        }else{
            if(root.left == null){
                return root.right;
            }else if(root.right == null){
                return root.left;
            }
            
            TreeNode minNode = findMin(root.right);
            root.val = minNode.val;
            root.right = deleteNode2(root.right, root.val);
        }
        return root;
    }

    private TreeNode findMin(TreeNode node){
        while(node.left != null){
            node = node.left;
        }
        return node;
    }
    
}
